/*
 * @lc app=leetcode.cn id=876 lang=typescript
 *
 * [876] 链表的中间结点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

//  思路：快慢指针
//  复杂度：O(n) O(1)

function middleNode(head: ListNode | null): ListNode | null {
    let fast = head, slow = head
    while (slow && fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
    }
    return slow
};
// @lc code=end

import { ListNode } from './type'
let l1 = new ListNode(1, new ListNode(2, new ListNode(3)))
let l2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))))
console.log(middleNode(l1)?.val);
console.log(middleNode(l2)?.val);
